package A_review.review6_30;

import java.util.Random;

public class QuickSort {

    public  int[]  quickSort(int[] nums){
   if (nums.length==0){
       return nums;
   }
   sort(nums,0, nums.length-1);
   return  nums;
    }



//todo:下面这个也是需要的
    // 洗牌算法，将输入的数组随机打乱
    private void shuffle(int[] nums) {
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    public  void  sort(int[] nums,int lo,int hi){
        if (lo>hi){
            return;
        }
        int i = find(nums, lo, hi);
        sort(nums,lo,i-1);
        sort(nums,i+1,hi);
    }


    public  int find(int[] nums,int lo,int hi){
        int partition=lo;
        int j=lo+1;
        int k=hi;
        while (j<=k){
            while (j<hi&&nums[j]<=nums[partition]){
                j++;
            }
            while (k>lo&&nums[k]>nums[partition]){
                k--;
            }
            if (j>=k){
                break;
            }
            swap(nums,j,k);
        }
        swap(nums,lo,k);
        //todo:返回的是这个大的一侧
        return  k;
    }

    public  void swap(int[] nums,int j,int k){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

}
